# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName  :practice1.py
# @Time      :2025/6/13 22:04
# @Author    :aiyimu
from typing import List


class SlidingWindow:
    # (3. 无重复字符的最长子串)[https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/]
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        t_hash = {}  # 哈希表，用于记录字符的出现次数
        n = len(s)  # 字符串的长度

        left = 0  # 滑动窗口的左边界
        ret_len = 0  # 最长子串的长度

        for right in range(n):  # 滑动窗口的右边界
            # 如果字符在哈希表中已存在，说明出现了重复字符
            while s[right] in t_hash and t_hash[s[right]] > 0:
                # 移动左边界，缩小窗口，直到去除重复字符
                t_hash[s[left]] -= 1
                left += 1

            # 将当前字符加入哈希表
            t_hash[s[right]] = t_hash.get(s[right], 0) + 1

            # 计算当前子串的长度，并更新最长子串的长度
            ret_len = max(ret_len, right - left + 1)

        return ret_len

    # (209. 长度最小的子数组)[https://leetcode.cn/problems/minimum-size-subarray-sum/description/]
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0:
            return 0

        left = 0
        cur_sum = 0
        ret_len = float('inf')

        for right in range(n):
            cur_sum += nums[right]

            # 找到和大于等于 target 的子数组，收缩左边界
            while cur_sum >= target:
                ret_len = min(ret_len, right - left + 1)
                cur_sum -= nums[left]
                left += 1

        return ret_len if ret_len != float('inf') else 0

    # (1004. 最大连续1的个数 III)[https://leetcode.cn/problems/max-consecutive-ones-iii/description/]
    def longestOnes(self, nums: List[int], k: int) -> int:
        if not nums:
            return nums

        n = len(nums); zero = 0 # 当前窗口内0的个数
        left = 0; right = 0
        ret_len = 0
        while right < n:
            if nums[right] == 0:
                zero += 1
            while zero > k:
                if nums[left] == 0:
                    zero -= 1
                left += 1
            ret_len = max(ret_len, right - left + 1)
            right += 1

        return ret_len

    # (1658. 将 x 减到 0 的最小操作数)[https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/]
    def minOperations(self, nums: List[int], x: int) -> int:
        total = sum(nums);
        target = total - x
        # 找和为target的长度最长的子数组
        n, ret_len, cur_sum = len(nums), -1, 0
        left, right = 0, 0

        if target < 0:  # x过大，减不到0
            return -1

        while right < n:
            cur_sum += nums[right]
            while cur_sum > target:
                cur_sum -= nums[left]
                left += 1
            if cur_sum == target:
                ret_len = max(ret_len, right - left + 1)
            right += 1

        if ret_len == -1:  # 减不到0
            return -1

        return n - ret_len

    # (904. 水果成篮)[https://leetcode.cn/problems/fruit-into-baskets/description/]
    def totalFruit(self, fruits: List[int]) -> int:
        if not fruits:
            return 0

        # 找“只有两种数”的最长的子数组
        left, right = 0, 0
        ret_len = 0
        kinds = {}  # 数组中水果种类
        while right < len(fruits):
            # 获取当前水果种类的数量，若不存在则默认值为0
            kinds[fruits[right]] = kinds.get(fruits[right], 0) + 1

            # 当种类数大于2时，缩小窗口
            while len(kinds) > 2:
                kinds[fruits[left]] -= 1
                if kinds[fruits[left]] == 0:
                    del kinds[fruits[left]]  # 删除水果种类
                left += 1

            # 更新结果
            ret_len = max(ret_len, right - left + 1)
            right += 1

        return ret_len

    # (LCR 015. 找到字符串中所有字母异位词)[https://leetcode.cn/problems/VabMRr/submissions/636987042/]
    def findAnagrams1(self, s, p):  # 字符串长度过长时超时
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """

        s_len, p_len = len(s), len(p)
        if s_len < p_len:
            return []

        # 判断两个字符串是否是变位词
        def are_anagrams(str1, str2):
            return Counter(str1) == Counter(str2)

        left, right = 0, 0
        cur_s = "";
        ret = []
        while right < s_len:
            cur_s += s[right]
            while len(cur_s) == p_len:
                if are_anagrams(cur_s, p) is True:
                    ret.append(left)
                left += 1
                cur_s = cur_s[1:]  # 从字符串的左边移除一个字符
            right += 1

        return ret

    def findAnagrams2(self, s, p):  # 滑动窗口，避免超时
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """

        s_len, p_len = len(s), len(p)
        if s_len < p_len:
            return []

        # 记录 p 的字符频率
        p_count = [0] * 26
        for c in p:
            p_count[ord(c) - ord('a')] += 1

        # 当前窗口字符频率
        cur_count = [0] * 26
        ret = []
        # 记录第一个窗口的频率
        for i in range(p_len):
            cur_count[ord(s[i]) - ord('a')] += 1
        # 第一个窗口就符合，添加到结果
        if cur_count == p_count:
            ret.append(0)

        for i in range(p_len, s_len):
            # 加入新字符
            cur_count[ord(s[i]) - ord('a')] += 1
            # 移除旧字符
            cur_count[ord(s[i - p_len]) - ord('a')] -= 1

            if cur_count == p_count:
                ret.append(i - p_len + 1)

        return ret

    # (30. 串联所有单词的子串)[https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/]
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        # 获取每个单词的长度和单词数量
        word_len = len(words[0])
        word_count = len(words)

        # 如果单词的总长度大于s的长度，直接返回空列表
        if word_len * word_count > len(s):
            return []

        # 统计 words 中每个单词的出现次数
        hash2 = defaultdict(int)
        for word in words:
            hash2[word] += 1

        ret = []

        # 遍历每个字符位置，进行分组查找
        for i in range(word_len):  # 执行len次
            hash1 = defaultdict(int)
            left = i
            count = 0

            # 遍历字符串 s 的每个子串
            for right in range(i, len(s) - word_len + 1, word_len):
                # 获取当前窗口的单词
                word = s[right:right + word_len]

                # 如果当前单词在 hash2 中，更新 hash1 并增加有效单词计数
                if word in hash2:
                    hash1[word] += 1
                    if hash1[word] <= hash2[word]:
                        count += 1

                # 当窗口大小超过 words 总长度时，移出左边的单词
                if right - left + word_len > word_len * word_count:
                    left_word = s[left:left + word_len]
                    if left_word in hash2:
                        hash1[left_word] -= 1
                        if hash1[left_word] < hash2[left_word]:
                            count -= 1
                    left += word_len

                # 如果有效的单词个数等于 words 数量，说明匹配成功
                if count == word_count:
                    ret.append(left)

        return ret

    # (76. 最小覆盖子串) [https://leetcode.cn/problems/minimum-window-substring/description/]
    def minWindow(self, s: str, t: str) -> str:
        # 初始化哈希表
        hash_t = [0] * 128;
        hash_cur = [0] * 128
        kinds = 0  # t中字符的种类

        # 统计t中每个字符的频率，更新
        for ch in t:
            if hash_t[ord(ch)] == 0:
                kinds += 1
            hash_t[ord(ch)] += 1

        min_len = float('inf')  # 最小字串的长度初始化为无穷大
        begin = -1  # 最小字串的起始位置
        left = 0  # 左指针
        count = 0  # 当前窗口中满足条件的字符种类
        # 滑动窗口
        for right in range(len(s)):
            in_char = s[right]
            hash_cur[ord(in_char)] += 1

            # 当前字符频率与t相同
            if hash_cur[ord(in_char)] == hash_t[ord(in_char)]:
                count += 1

            while count == kinds:
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    begin = left

                # 收缩窗口
                out_char = s[left]
                hash_cur[ord(out_char)] -= 1
                if hash_cur[ord(out_char)] < hash_t[ord(out_char)]:
                    count -= 1
                left += 1
        # 如果没有满足条件的字串，返回空字符串
        return "" if begin == -1 else s[begin:begin + min_len]

